package book;


public class BinarySearchSolution {
    
    // 二分搜索，在非降序序列a中搜索x
    int binarySearch(int[] a, int x) {
        int left = 0, right = a.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (x > a[mid])
                left = mid + 1; // x位于mid右边，调整左边界
            else if (x < a[mid])
                right = mid - 1; // x位于mid左边，调整右边界
            else
                return mid; // 找到x，返回当前位置
        }
        return -1; // 搜索完毕，未找到x，返回-1
    }
    /**
     * 二分搜索 - 常规解法（递归）
     */
    int search(int[] nums, int target, int start, int end) {
        if (start > end) return -1;
        if (start == end) return nums[start] == target ? start : -1;
        int mid = start + (end - start) / 2;
        if (nums[mid] == target) return mid;
        else if (target < nums[mid]) 
            return search(nums, target, start, mid - 1);
        else // if target > nums[mid] 
            return search(nums, target, mid + 1, end);
    }

    /**
     * 力扣704 - 题目说了没有重复的元素，因此用常规（简化版）方法可解
     * 但我们应该进一步研究，对于更一般的情况，我们应该如何用二分搜索，并且找出所有的target
     */
    public int search(int[] nums, int target) {
        // 常规解法
        return search(nums, target, 0, nums.length - 1);

        // 使用下界模板
        // int lb = lowerBound(nums, target);
        // return nums[lb] == target ? lb : -1;

        // 使用上界模板
        // int ub = upperBound(nums, target);
        // return nums[ub] == target ? ub : -1;

        // 上下界模板一起用
        // int lb = lowerBound(nums, target), ub = upperBound(nums, target);
        // return ub >= lb ? lb : -1;
    }

    /**
     * 下界模板
     * 下界的定义：数组中大于等于target的第一个元素下标位置
     * 当target存在多个时，下界取到最左边的元素
     * 当target不存在时，下界表示target在排序数组中的插入位置
     */
    int lowerBound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) / 2; // 注意这里不要记错成上界模板的(left+right+1)/2，否则同样会掉入死循环陷阱
            if (nums[mid] < target)
                left = mid + 1;
            else 
                right = mid;
        }
        return left;
    }

    /**
     * 上界模板
     * 上界的定义：数组中小于等于target的最后一个元素下标位置
     * 当target存在多个时，上界取到最右边的元素
     * 当target不存在时，上界表示target在排序数组中的插入位置之前的位置
     */
    int upperBound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = (left + right + 1) / 2; // 小心死循环陷阱，这里记得+1
            if (nums[mid] > target)
                right = mid - 1;
            else 
                left = mid;
        }
        return left;
    }

    // 演示：通过上界和下界求目标值的总个数
    void test() {
        int[] a = { 1, 2, 3, 3, 3, 4, 5, 6 };
        int t = 3;
        int lb = lowerBound(a, t), ub = upperBound(a, t);
        System.out.println("数组搜索的下界是" + lb + ", 上界是" + ub + ", 目标元素总共有" + (ub - lb + 1) + "个");
    }

    public static void main(String[] args) {
        BinarySearchSolution sln = new BinarySearchSolution();
        sln.test();
    }
}
